// 有装下8个苹果的袋子、装下6个苹果的袋子，一定要保证买苹果时所有使用的袋子都装满
// 对于无法装满所有袋子的方案不予考虑，给定n个苹果，返回至少要多少个袋子
// 如果不存在每个袋子都装满的方案返回-1

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <ctime>

using namespace std;

const int INF = 0x3f3f3f3f;

// 当前还有 rest 个苹果，使用的每个袋子必须装满，返回至少几个袋子
int f(int rest)
{
    if(rest < 0) return INF;
    if(rest == 0) return 0;

    // 使用8规格的袋子，剩余的苹果还需要几个袋子，有可能返回无效解
    int p1 = f(rest - 8);
    // 使用6规格的袋子，剩余的苹果还需要几个袋子，有可能返回无效解
    int p2 = f(rest - 6);
    p1 += p1 != INF ? 1 : 0;
    p2 += p2 != INF ? 1 : 0;
    return min(p1, p2); 
}

int bags1(int apple)
{
    int ans = f(apple);
    return ans == INF ? -1 : ans;
}

int bags2(int apple)
{
    if(apple & 1) return -1;
    if(apple < 18)
    {
        if(apple == 0) return 0;
        if(apple == 6 || apple == 8) return 1;
        if(apple == 12 || apple == 14 || apple == 16) return 2;
        return -1;
    }
    return (apple - 18) / 8 + 3;
}

int main()
{
    srand(time(nullptr));
    for(int apple = 0; apple < 100; ++apple)
    {
        cout << apple << " : " << bags1(apple) << endl;
    }
    return 0;
}